package com.douma.practice;


public class QuickSort {

    private int[] data;

    public void sort(int[] data) {
        this.data = data;
        dfs(0, data.length - 1);
    }

    private void dfs(int start, int end) {
        if (start >= end) return;

        // 分区
        int j = partition(start, end);

        dfs(start, j - 1);
        dfs(j + 1, end);
    }

    private int partition(int start, int end) {
        int pivot = data[end];
        int less = start;
        int great = start;
        for (; great <= end - 1; great++) {
            if (data[great] < pivot) {
                swap(data, less, great);
                less++;
            }
        }
        swap(data, less, end);
        return less;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}
